package leetcode.pre50;

import leetcode.top100.Code11_GetMaxWater_装水最多的容器;
import leetcode.top100.Code84_MaxRectangleArea1;

/**
 * 见{@link Code11_GetMaxWater_装水最多的容器}
 * 见{@link Code42_MaxWater_接雨水}
 * 见{@link Code84_MaxRectangleArea1}
 *
 * @date 2020/4/1 22:56
 */
public class Code42_MaxWater_接雨水 {
    public int trap(int[] height) {
        if (height == null || height.length <= 2) return 0;
        int lmax = height[0];
        int rmax = height[height.length - 1];
        int l = 1;
        int r = height.length - 2;
        int water = 0;
        while (l <= r) {
            //更新小的那一侧
            if (lmax < rmax) {
                water += lmax >= height[l] ? lmax - height[l] : 0;
                lmax = Math.max(lmax, height[l++]);
            } else {
                water += rmax >= height[r] ? rmax - height[r] : 0;
                rmax = Math.max(rmax, height[r--]);
            }

        }
        return water;
    }
}